﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algo
{
    class Sorter
    {
        //function partition(array, left, right, pivotIndex)
        //pivotValue := array[pivotIndex]
        //swap array[pivotIndex] and array[right]  // Move pivot to end
        //storeIndex := left
        //for i from left to right - 1  // left ≤ i < right
        //if array[i] < pivotValue
        //swap array[i] and array[storeIndex]
        //storeIndex := storeIndex + 1
        //swap array[storeIndex] and array[right]  // Move pivot to its final place
        //return storeIndex
        private int Partition(int[] array, int l, int r, int pivotIndex)
        {
            int pivotValue = array[pivotIndex];
            Swap(array, pivotIndex, r);
            int storeIndex = l;
            for (int i = l; i < r; i++)
            {
                if (array[i] < pivotValue)
                {
                    Swap(array, i, storeIndex);
                    storeIndex++;
                }
            }
            Swap(array, storeIndex, r);
            return storeIndex;
        }

        private void Swap(int[] array, int i, int j)
        {
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }

        protected void QuickSort(int[] array, int l, int r)
        {
            if (r <= l)
            {
                return;
            }

            // pick pivot
            Random rd = new Random();
            int pivot = rd.Next(l, r);
            //int pivot = 0;
            int newPivot = Partition(array, l, r, pivot);
            QuickSort(array, l, newPivot);
            QuickSort(array, newPivot + 1, r);

        }

        public void Play()
        {
            int[] array = new int[] { 3, 2, 1, 5, 4 };
            Console.WriteLine("\nOriginal array");
            printArray(array);
            QuickSort(array, 0, array.Length - 1);
            Console.WriteLine("\nSorted array");
            printArray(array);
        }

        private void printArray(int[] a)
        {
            foreach (int i in a)
            {
                Console.Write(i + "\t");
            }
        }
    }
}
